Longest common subsequences and the Bernoulli matching model: numerical work and analyses of the r-reach simplification

摘要

The expected length of longest common subsequences is a problem that has beenin the literature for at least twenty five years. Determining the limitingconstants \gamma_k appears to be quite difficult, and the current best boundsleave much room for improvement. Boutet de Monvel explores an independentversion of the problem he calls the Bernoulli Matching model. He explores thisproblem and its relation to the longest common subsequence problem. This papercontinues this pursuit by focusing on a simplification we term r-reach. For thestring model, L_r(u,v) is the longest common subsequence of u and v given thateach matched pair of letters is no more than r letters apart.